import DoublyLinkedList from '../data-structures/doubly-linked-list';
import { DoublyNode } from '../data-structures/models/linked-list-models';

//lru最少最近算法，O(1)时间复杂度
export class lruCache{
  map:Map<any,DoublyNode<any>>
  doublyLinkedList:DoublyLinkedList<any>
  constructor(public limit:number = 6){
    this.map = new Map();
    this.doublyLinkedList = new DoublyLinkedList();
  }
  get(key:any){
    if(this.map.has(key)) {
      let node  = this.map.get(key);
      if((node as DoublyNode<any>).prev){
        ((node as DoublyNode<any>).prev as DoublyNode<any>).next = node?.next;
      }
      if((node as DoublyNode<any>).next){
        ((node as DoublyNode<any>).next as DoublyNode<any>).prev = node?.prev
      }
      this.doublyLinkedList.deCount();
      //链表中移除node并更新节点到头部
      this.doublyLinkedList.insert({key,value:node?.element.value},0);
      return node?.element
    }
    return -1
  }
  set(key:any,value:any){
    if(this.map.has(key)) {
      let node = this.map.get(key);
      if((node as DoublyNode<any>).prev){
        ((node as DoublyNode<any>).prev as DoublyNode<any>).next = node?.next;
      }
      if((node as DoublyNode<any>).next){
        ((node as DoublyNode<any>).next as DoublyNode<any>).prev = node?.prev
      }
      this.doublyLinkedList.deCount();
      //链表中移除node并更新节点到头部
      this.doublyLinkedList.insert({key,value},0);
    }else{
      this.doublyLinkedList.insert({key,value},0);
      const node = this.doublyLinkedList.getHead();
      if(this.map.size>=this.limit){
        const node = this.doublyLinkedList.removeAt(this.doublyLinkedList.size()-1);
        this.map.delete(node.key)
      }
      this.map.set(key,node as DoublyNode<any>)
    }
  }
}